For data transmission systems, for example, communication systems or digital storage systems, the transmitted signals from a transmitter are prone to influences of noises. Thereby, received signals at a receiver include error data. In order to solve the problem, according to the prior art, data to be transmitted and extra data are encoded to signals to be transmitted from the transmitter. The receiver then decodes the received signals according to corresponding decoding method, and thereby acquires exact data. The method described above is named forward error control (FEC) method. In various FEC methods, low-density parity-check codes are codes usually used.
Low-density parity-check codes, which are a kind of block codes, are proposed by R. G. Gallager in 1963. An (n, k) 2-bit linear low-density parity-check code is defined, where n is the length of the block code and k is the bit-length of a message within the block code. Moreover, a parity-check matrix H, which is a M-by-N matrix, is simplified to be a (n-k)-by-n sparse matrix. The number of elements with value 1 in each row and column of the parity-check matrix is very small with respect to the length of the block code n. Thereby, the codes are named as low-density parity-check codes.
FIG. 1 shows a block diagram of a transmission system with low-density parity-check codes according to a preferred embodiment of the present invention. As shown in the figure, the transmission system includes a transmission apparatus 1′ and a receiving apparatus 2′. The transmission apparatus 1′ includes an encoding unit 10′ and a modulation unit 12′. The encoding unit encodes data; the modulation unit 12′ modulates encoded data by the encoding unit 10′, and transmits it to the receiving apparatus 2′. The receiving apparatus 2′ includes a demodulation unit 20′ and a decoding unit 22′. The demodulation unit 20′ demodulates the data transmitted by the transmitting apparatus 1′ according to the corresponding modulation method of the modulation unit 12′. Then, the decoding unit 22′ decodes the data demodulated by the demodulation unit 20′ to recover required data.
The encoding unit 10′ adopts low-density parity-check codes for encoding. The low-density parity-check encoding method is the same as the general block encoding. A codeword vector is given by multiplying the message passing sent into the encoding unit 10′ by a codeword generator matrix. In addition, the multiplication of the transposes of the codeword vector (a row matrix) and of the parity-check matrix is zero, that is, CT·HT=0. (Alternatively, the multiplication of the parity-check matrix and the codeword vector (a column matrix) is zero, that is, H·C=0.) If the received codeword is affected by channel noises, then the multiplication of the transposes of the received codeword and of the parity-check matrix is no longer a zero vector, and is defined as a syndrome vector. Checking if the syndrome vector is zero tells if the received codeword is correct or not.
In addition, the decoding unit 22′ uses the decoding method of low-density parity-check codes. Low-density parity-check coding is an application of belief propagation (BP) algorithm, which uses the message passing between message nodes and check nodes as repeated decoding. FIG. 2 shows the decoding procedure of low-density parity-check codes. At first, use the received codeword vector to initialize the posterior probability of the message nodes. Then, update the probabilities of the message nodes and the check nodes repeatedly. Finally, calculate the confidence of the message nodes to make decoding decision {circumflex over (x)}. If the multiplication of the decoding decision {circumflex over (x)} and the transpose of the parity-check matrix is zero, that is, {circumflex over (x)}·HT=0, then the decoding is successful. Otherwise, if the maximum number of repeat is reached, the decoding is failed; if the maximum number of repeat is not reached yet, continue updating repeatedly until decoding is successful or the maximum number of repeat is reached.
In the process of the BP-based algorithm according to the prior art, the minimum and the next minimum values of r input values are used for calculation to produce r output values. According to the prior art, the method to get the minimum and the next minimum values from r input values is: compare to get a minimum value from r input values; then, use the other values to compare and search a next minimum value. That is, the minimum value is searched first, and then the next minimum value is searched.
Related prior arts can be referred as follows:    1. J. Chen et al., “Reduced-Complexity Decoding of LDPC Codes”, IEEE Trans. On Communications, vol. 53, No. 8, pp. 1288-1299, 2005;    2. D. E. Kunth, The Art of Computer Programming. Reading, Mass.: Addison Wesley, 1973, vol. 3, pp. 209-242; and    3. U.S. Patent Pub. No. U.S.2004/0153959 A1 “LDPC Decoding Apparatus and Method”.